package data_structure.video;

/**
 * 双向链表的使用
 */
class BidirectionalLinkedList {
    private Student head = new Student(null,0,"",null);//头指针

    //添加
    public void insert(Student stu){
        //创建头指针
        Student temp = head;
        //如果指针的下一个指向不为空,代表没有找到最后一个位置,继续查找
        while (temp.next != null){
            temp = temp.next;
        }
        //找到最后一个链表位置，下一个位置为空
        //添加操作:1.让最后一个位置的next指向新插入结点
        //2.让新插入的pre指向最后一个位置
        temp.next = stu;
        stu.pre = temp;
    }

    //删除
    //需要考虑删除的是不是头结点 ->头指针 向后一个 (当前不需要考虑，因为头指针不做任何操作)
    //考虑删除是不是尾部结点 -> 前一个指针指向空
    //考虑删除中间的结点 ->前一个指针 指向 当前位置 的下一个位置 ->后一个指针 指向 当前位置 的前一个位置
    public void delete(Student stu){
        //创建头指针
        Student temp = head;
        while (temp != null){
            //temp 需要指向 被删除结点的前一个结点,所以需要 双指针进行操作
            Student temp1 = temp.next;
            //找到需要被删除结点
            //补充：如果需要删除最后一个 需要判断删除结点是不是最后一个，如果是，前面一个结点的next指向null
            if (temp1 == stu) {
                //结点为最后一个
                if (temp1.next == null) {
                    temp.next = null;
                    return;
                }
                //找到需要被删除对象的下一个结点
                temp1 = temp1.next;
                temp.next = temp1;
                temp1.pre = temp;
                return;
            }
            temp = temp.next;
        }
    }

    //遍历链表
    public void ergodic(){
        int size = 0;
        //创建头指针
        Student temp = head;
        //如果指针的下一个指向不为空，代表还没有找到最后一个位置
        while (temp.next != null){
            temp = temp.next;
            System.out.println(temp);
            size++;
        }
        System.out.println("链表当中数据共有: "+size);
    }

    static class Student{
        private Student pre;//头指针
        private int id;
        private String name;
        private Student next;//尾指针

        public Student(Student pre, int id, String name, Student next) {
            this.pre = pre;
            this.id = id;
            this.name = name;
            this.next = next;
        }

        public Student() {
        }

        @Override
        public String toString() {
            return "Student{" +
                    "id=" + id +
                    ", name='" + name + '\'' +
                    '}';
        }
    }

}

class BidirectionalLinkedListDemo{
    public static void main(String[] args) {
        BidirectionalLinkedList list = new BidirectionalLinkedList();
        BidirectionalLinkedList.Student s1 = new BidirectionalLinkedList.Student(null,1,"张三",null);
        BidirectionalLinkedList.Student s2 = new BidirectionalLinkedList.Student(null,2,"李四",null);
        BidirectionalLinkedList.Student s3 = new BidirectionalLinkedList.Student(null,3,"王五",null);
        list.insert(s1);
        list.insert(s2);
        list.insert(s3);
        System.out.println("遍历结点...");
        list.ergodic();
        System.out.println("删除结点...");
        list.delete(s1);
        list.ergodic();
    }
}


